package tree.binaryTree;

import lombok.NoArgsConstructor;
import tree.threadedBinaryTree.ThreadBinaryTree;

/**
 * 此代码仅仅包含了二叉树的前中后序遍历
 * 功能：
 * 1）前中后序遍历
 * 2）前中后序查找id
 * 3）根据id删除节点V1（简单性删除，如果是叶子节点直接删，如果是非叶子节点，删除整棵树）
 */
public class BinaryTree {
    public static void main(String[] args) {

        BinaryTree binaryTree = new BinaryTree();
        HeroNode root = new HeroNode(1, "松江");
        HeroNode node1 = new HeroNode(2, "吴用");
        HeroNode node2 = new HeroNode(3, "陆军");
        HeroNode node3 = new HeroNode(4, "林冲");
        HeroNode node4 = new HeroNode(5, "老虎");
        HeroNode node5 = new HeroNode(6, "华强");
        binaryTree.setRoot(root);
        root.setLeft(node1);
        root.setRight(node2);
        node1.setLeft(node3);
        node2.setRight(node4);
        node2.setLeft(node5);
        System.out.println("二叉树的前序遍历");
        binaryTree.preOrder();
        System.out.println("二叉树的中序遍历");
        binaryTree.infixOrder();
        System.out.println("二叉树的后序遍历");
        binaryTree.postOrder();
        binaryTree.preOrderSearch(13);
        binaryTree.infixOrderSearch(3);
        binaryTree.postOrderSearch(2);
        binaryTree.preOrder();
        System.out.println("开始删除操作");
        binaryTree.deleteById(3);
        binaryTree.preOrder();
    }

    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public HeroNode getRoot() {
        return root;
    }

    /**
     * 前序遍历方法
     */
    public void preOrder() {
        if (root != null) {
            this.root.preOrder();
        } else System.out.println("二叉树为空，无法遍历");
    }

    /**
     * 中学遍历
     */
    public void infixOrder() {
        if (root != null) {
            this.root.infixOrder();
        } else System.out.println("二叉树为空，无法遍历");
    }

    public void postOrder() {
        if (root != null) {
            this.root.postOrder();
        } else System.out.println("二叉树为空，无法遍历");
    }

    public void preOrderSearch(int id) {
        HeroNode node = null;
        if (root != null) {
            node = this.root.preOrderSearch(id);
        }
        if (null == node) {
            System.out.println("查无此人");
        } else {
            System.out.println(node);
        }
    }

    public void infixOrderSearch(int id) {
        HeroNode node = null;
        if (root != null) {
            node = this.root.infixOrderSearch(id);
        }
        if (null == node) {
            System.out.println("查无此人");
        } else {
            System.out.println(node);
        }
    }

    public void postOrderSearch(int id) {
        HeroNode node = null;
        if (root != null) {
            node = this.root.postOrderSearch(id);
        }
        if (null == node) {
            System.out.println("查无此人");
        } else {
            System.out.println(node);
        }
    }

    /**
     * 二叉树删除节点Version1：1）如果删除的是叶子节点，直接删除
     * 2）如果删除的是非叶子节点，删除整棵树
     */
    public void deleteById(int id) {
        if (root == null) {
            System.out.println("该二叉树为空");
            return;
        }
        if (this.root.getId() == id) {
            System.out.println("删除的是root节，删除整棵树");
            this.root = null;
            return;
        }
        root.deleteById(id);
    }

    /**
     * 二叉树删除节点Version1：1）如果删除的是叶子节点，直接删除
     * 2）如果删除的是非叶子节点，如果该非叶子节点A只有一个叶子节点B，则子节点B代替A
     * 如果该叶子节点A有左子节点B和右子节点C，则让C代替A。
     */
    public void deleteByIdV2(int id) {
        if (root == null) {
            System.out.println("该二叉树为空");
            return;
        }
        if (this.root.getId() == id) {
            System.out.println("删除的是root节，删除整棵树");
            this.root = null;
            return;
        }
        root.deleteByIdV2(id);
    }


    @lombok.Data
    @NoArgsConstructor
    static
            /**
             * 这只是创建一个节点
             */
    class HeroNode {
        private int id;
        private String name;
        private HeroNode left;
        private HeroNode right;

        public HeroNode(int id, String name) {
            this.id = id;
            this.name = name;
        }

        @Override
        public String toString() {
            return "HeroNode{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    '}';
        }

        /**
         * 前序遍历
         */
        public void preOrder() {
            System.out.println(this);
            if (this.left != null) {
                this.left.preOrder();
            }
            if (this.right != null) {
                this.right.preOrder();
            }
        }

        /**
         * 中序遍历
         */
        public void infixOrder() {
            if (this.left != null) {
                this.left.infixOrder();
            }
            System.out.println(this);
            if (this.right != null) {
                this.right.infixOrder();
            }

        }

        /**
         * 后序遍历
         */
        public void postOrder() {
            if (this.left != null) {
                this.left.postOrder();
            }
            if (this.right != null) {
                this.right.postOrder();
            }
            System.out.println(this);
        }

        /**
         * 前序遍历寻找指定id，输出的话为比较次数
         */
        public HeroNode preOrderSearch(int id) {
            System.out.println("前序遍历");
            HeroNode node = null;
            if (this.id == id) {
                return this;
            }
            if (this.left != null) {
                node = this.left.preOrderSearch(id);
            }
            if (null != node) {
                return node;
            }
            if (this.right != null) {
                node = this.right.preOrderSearch(id);
            }
            return node;
        }

        /**
         * 中序遍历寻找指定id，输出的话为比较次数
         */
        public HeroNode infixOrderSearch(int id) {
            HeroNode node = null;
            if (this.left != null) {
                node = this.left.infixOrderSearch(id);
            }
            if (null != node) {
                return node;
            }
            System.out.println("中序遍历");
            if (this.id == id) {
                return this;
            }
            if (this.right != null) {
                node = this.right.infixOrderSearch(id);
            }
            return node;
        }

        /**
         * 后序遍历寻找指定id，输出的话为比较次数
         */
        public HeroNode postOrderSearch(int id) {
            HeroNode node = null;
            if (this.left != null) {
                node = this.left.postOrderSearch(id);
            }
            if (null != node) {
                return node;
            }
            if (this.right != null) {
                node = this.right.postOrderSearch(id);
            }
            if (node != null) {
                return node;
            }
            System.out.println("后序遍历");
            if (this.id == id) {
                return this;
            }
            return null;
        }

        /**
         * 根据id删除节点;思路：
         * 1）因为我们的二叉树是单向的，所以我们是判断当前节点的子节点是否是需要删除的节点。
         * 2）如果左子节点不为空 && 左子节点就是要删除的  ， this.left =null return;
         * 3）如果右子节点不为空 && 右子节点就是要删除的  ， this.right =null return;
         * 4）如果2，3没找到，则对左子树进行递归删除
         * 5）如果4也没删掉，对右子树递归删除
         */
        public void deleteById(int id) {
            if (this.left != null && this.left.getId() == id) {
                this.left = null;
                System.out.println(true);
                return;
            }
            if (this.right != null && this.right.getId() == id) {
                this.right = null;
                System.out.println(true);
                return;
            }
            if (this.left != null) {
                this.left.deleteById(id);
            }
            if (this.right != null) {
                this.right.deleteById(id);
            }
        }

        /**
         * 一个新的课后习题：
         * question：如果要删除的节点是非叶子节点，不是删除整棵树而是采用下面规则：
         * 如果该非叶子节点A只有一个叶子节点B，则子节点B代替A
         * 如果该叶子节点A有左子节点B和右子节点C，则让C代替A。
         * 代码有点乱...
         */
        public void deleteByIdV2(int id) {
            if (this.left != null && this.left.getId() == id) {
                // 叶子节点
                if (this.left.left == null && this.left.right == null) {
                    this.left = null;
                    // 非叶子节点
                } else {
                    // 只有一个子节点
                    if (this.left.left == null || this.left.right == null) {
                        if (this.left.left == null) {
                            this.left = this.left.right;
                        } else {
                            this.left = this.left.left;
                        }
                    }
                    // 有二个子节点
                    if (this.left.left != null && this.left.right != null) {
                        this.left.right.left = this.left.left;
                        this.left = this.left.right;
                    }
                }
                System.out.println(true);
                return;
            }
            if (this.right != null && this.right.getId() == id) {
                // 叶子节点
                if (this.right.left == null && this.right.right == null) {
                    this.right = null;
                    // 非叶子节点
                } else {
                    // 只有一个节点
                    if (this.right.left == null || this.right.right == null) {
                        if (this.right.left == null) {
                            this.right = this.right.right;
                        } else {
                            this.right = this.right.left;
                        }
                    }
                    // 拥有二个节点
                    if (this.right.left != null && this.right.right != null) {
                        this.right.right.left = this.right.left;
                        this.right = this.right.right;
                    }
                }
                System.out.println(true);
                return;
            }

            if (this.left != null) {
                this.left.deleteById(id);
            }
            if (this.right != null) {
                this.right.deleteById(id);
            }
        }
    }
}


